package com.wangyadong.hobby.schedule.jobtask.tree.pq;


import java.util.ArrayList;
import java.util.Comparator;

/**
 * <p>
 *
 * @author <714037465@qq.com>
 * @since 2018/8/2913:13
 **/
public class HeapPriorityQueue<K, V> extends AbstractPriorityQueue<K, V> {

    protected ArrayList<Entry<K, V>> heap = new ArrayList<>();

    public HeapPriorityQueue() {
        super();
    }

    public HeapPriorityQueue(Comparator comparator) {
        super(comparator);
    }

    protected int parent(int j) {
        return (j - 1) / 2;
    }

    protected int left(int j) {
        return 2 * j + 1;
    }

    protected int right(int j) {
        return 2 * j + 2;
    }

    ///
    protected boolean hasLeft(int j) {
        return left(j) < heap.size();
    }

    protected boolean hasRight(int j) {
        return right(j) < heap.size();
    }

    protected void swap(int i, int j) {
        Entry<K, V> temp = heap.get(i);
        heap.set(i, heap.get(j));
        heap.set(j, temp);
    }

    protected void upHead(int j) {
        while (j > 0) {
            int parent = parent(j);
            if (compare(heap.get(j), heap.get(parent)) >= 0) break;
            swap(j, parent);
            j = parent;
        }
    }

    protected void downHead(int j) {
        while (hasLeft(j)) {
            int leftIndex = left(j);
            int smallChildenIndex = leftIndex;
            if (hasRight(j)) {
                int rightIndex = right(j);
                if (compare(heap.get(leftIndex), heap.get(rightIndex)) >= 0) {
                    smallChildenIndex = rightIndex;
                }
            }
            if (compare(heap.get(smallChildenIndex), heap.get(j)) >= 0) {
                break;
            }
            swap(j, smallChildenIndex);
            j = smallChildenIndex;
        }
    }

    public int size() {
        return heap.size();
    }

    public Entry<K, V> min() {
        if (heap.isEmpty()) return null;
        return heap.get(0);
    }

    public Entry<K, V> insert(K k, V v) {
        checkKey(k);
        Entry<K, V> kvpqEntry = new PQEntry<K, V>(k, v);
        heap.add(kvpqEntry);
        upHead(heap.size() - 1);
        return kvpqEntry;
    }

    public Entry<K, V> removeMin() {
        if (heap.isEmpty()) {
            return null;
        }
        Entry<K, V> kvEntry = heap.get(0);
        swap(0, heap.size() - 1);
        downHead(0);
        return kvEntry;
    }

    public static void main(String[] args) {
        HeapPriorityQueue priorityQueue = new HeapPriorityQueue();
        priorityQueue.insert(9, "ee");
        priorityQueue.insert(2, "ee");
        priorityQueue.insert(-1, "ee");
        priorityQueue.insert(3, "ee");
        priorityQueue.insert(-8, "ee");
        priorityQueue.insert(10, "ee");
        priorityQueue.removeMin();
        System.out.println(priorityQueue.min().getKey());
    }

}
